package work.algorithm.tree;

import cn.hutool.json.JSONUtil;

import java.util.*;

/**
 * @author shenminglong@kedacom.com
 * @date 2021-11-30
 * 多级树的广度遍历
 */
public class TreeTest01 {

    public static void main(String[] args) {

        List<TreeEntity> list1 = new ArrayList<>();
        list1.add(new TreeEntity("111",null));
        list1.add(new TreeEntity("222",null));
        list1.add(new TreeEntity("333",null));
        list1.add(new TreeEntity("444",null));

        List<TreeEntity> list2 = new ArrayList<>();
        list2.add(new TreeEntity("888",null));
        list2.add(new TreeEntity("999",null));

        TreeEntity middle1 = new TreeEntity("middle1",list1);
        TreeEntity middle2 = new TreeEntity("middle2",list2);

        List<TreeEntity> rootList = new ArrayList<>();
        rootList.add(middle1);
        rootList.add(middle2);

        TreeEntity root = new TreeEntity("root",rootList);

        TreeTest01.bfs(root);

        System.out.println(JSONUtil.parse(root));
    }

    // 广度优先遍历
    public static void bfs(TreeEntity node) {
        if (node == null) {
            return;
        }
        Queue<TreeEntity> queue = new LinkedList<>();
        //用来注册已加入队列的节点——>防止重复添加节点
        HashSet<TreeEntity> set = new HashSet<>();
        queue.add(node);
        set.add(node);

         // 循环遍历
        while (!queue.isEmpty()) {
            TreeEntity cur = queue.poll();
            System.out.println(cur.value);


            List<TreeEntity> children = cur.getChildren();
            if(null!= children) {
                ListIterator<TreeEntity> iterator = children.listIterator();
                while (iterator.hasNext()) {
                    TreeEntity next = iterator.next();

                    // 当前结点的子结点是叶子结点
                    if(next.getChildren()==null) {

                        if(next.getValue().equals("222")) {
                            iterator.remove();
                        }
                        if(next.getValue().equals("333")) {
                            iterator.add(new TreeEntity("xyz_111",null));
                        }
                        System.out.println(next);
                    } else{
                        // 当前结点的子结点是非叶子结点
                    }

                    // 将节点的所有下游节点加入到队列
                    // 当前结点的子结点全部入队列
                    if (!set.contains(next)) {
                        set.add(next);
                        queue.add(next);
                    }
                }
            }
        }
    }


}
